import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给出一个区间的集合，请合并所有重叠的区间。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2:
 * <p>
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
class Solution {

    public static void main(String[] args) {
        // int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] intervals = new int[][]{{1, 4}};
        int[][] res = merge(intervals);
        for (int i = 0; i < res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }
    }

    public static int[][] merge2(int[][] intervals) {
        int len = intervals.length;
        List<int[]> lists = new ArrayList<int[]>();
        // 我遍历一遍找到里面的最小值，查询有没有和最小值相关的，有就合并，重复此操作到结束
        int[] x = new int[2];


        // 合并的时候还要把合并完的代入检验，合并操作可能会导致覆盖其他的，直到不覆盖为止
        lists.add(x);


        int[][] res = new int[lists.size()][2];
        for (int i = 0; i < lists.size(); i++) {
            res[i] = lists.get(i);
        }
        return res;
    }

    public static int[][] merge(int[][] intervals) {
        List<int[]> lists = new ArrayList<int[]>();
        // 用一个dp记录标记情况
        int len = intervals.length;
        int[] dp = new int[len];
        // 定义已处理
        int handled = 0;
        int tmp = -1;
        boolean swap;
        // 遍历每一个元素，看这个元素是不是没有和其他的相交，如果是就标记，不是就合并，继续遍历直到全部处理
        while (handled < len) {
            swap = false;
            for (int i = 0; i < len; i++) {
                // 如果当前还未处理
                if (dp[i] == 0) {
                    if (-1 == tmp) {
                        tmp = i;
                        swap = false;
                    } else if (tmp == i) {
                    } else {
                        // 对比当前值和tmp是否相交
                        if (Math.min(intervals[tmp][1], intervals[i][1]) >= Math.max(intervals[tmp][0], intervals[i][0])) {
                            intervals[tmp] = new int[]{Math.min(intervals[tmp][0], intervals[i][0]), Math.max(intervals[tmp][1], intervals[i][1])};
                            ++handled;
                            dp[i] = 1;
                            swap = true;
                        }

                    }
                }
            }
            if (!swap) {
                ++handled;
                dp[tmp] = 1;
                lists.add(intervals[tmp]);
                tmp = -1;
            }
        }
        return lists.toArray(new int[0][]);
    }

}